package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_060_PermutationSequence {
    public static void main(String[] args) {

    }

    static class Solution {
        public String getPermutation(int n, int k) {
            k--;

            List<Integer> numList = new ArrayList<>();
            for (int i = 1; i <= n; i++)
                numList.add(i);

            int factorial = 1;
            for (int i = 2; i < n; i++)
                factorial *= i;

            StringBuilder res = new StringBuilder();
            int times = n - 1;

            while (times >= 0) {
                int indexInList = k / factorial;
                res.append(numList.get(indexInList));
                numList.remove(indexInList);

                k = k % factorial;
                if (times != 0)
                    factorial = factorial / times;

                times--;
            }

            return res.toString();
        }
    }
}
